  class ListNode {
      int val;ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class demo {

    public ListNode mergeKLists(ListNode[] lists) {
        return mergegui(lists,0, lists.length-1);
    }
    public ListNode mergegui(ListNode[]lists ,int left,int right){
        if(left>right)return null;
        if(left==right)return lists[left];//得到链表的关键
        int mid=(left+right)/2;

        ListNode newhead=new ListNode();
        ListNode cur=newhead;

        ListNode lcut=mergegui(lists,left,mid);
        ListNode rcut=mergegui(lists,mid+1,right);

        while (lcut!=null&&rcut!=null){
            if(lcut.val<=rcut.val){
                cur.next=lcut;
                lcut=lcut.next;
            }else{
                cur.next=rcut;
                rcut=rcut.next;
            }
            cur=cur.next;//移动当前指针
        }
        if(lcut!=null)cur.next=lcut;
        if(rcut!=null)cur.next=rcut;
        return newhead.next;
    }
}
